package LeetcodeTest_eleven;
//打家劫舍III，动态规划
import java.util.*;

public class rob
{
    public static void main(String[] args)
    {
        TreeNode root=null;
        root=solution.createTree(root);
        System.out.println(solution.rob(root));
    }
}
class solution
{
    public static int rob(TreeNode root)
    {
        return Math.max(search(root,true),search(root,false));
    }
    public static int search(TreeNode t,Boolean flag)
    {
        if (t==null)
            return 0;
        if(flag==true)
        {
            flag=false;
            return t.val+search(t.left,flag)+search(t.right,flag);
        }
        else
            return Math.max(search(t.left,true),search(t.left,false))+Math.max(search(t.right,true),search(t.right,false));
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
   /* //二叉树的广度优先遍历，并输出每一层节点的和
    public static int rob(TreeNode root)
    {
        int i,j,sum,x;
        int result1,result2;
        i=sum=result1=result2=0;
        if(root==null)
            return 0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        ArrayList<Integer> summary=new ArrayList<Integer>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        int current=x=j=1;
        int next=0;
        queue.offer(root);
        while(!queue.isEmpty())
        {

            TreeNode tree=queue.poll();
            current--;
            if(tree.left!=null)
            {
                queue.offer(tree.left);
                next++;
            }
            if(tree.right!=null)
            {
                queue.offer(tree.right);
                next++;
            }
            list.add(tree.val);
            if(current==0)
            {
                for(i= list.size()-1;i>=list.size()-x;--i)
                    sum+=list.get(i);
                summary.add(sum);
                sum=0;
                current=next;
                x=current;
                next=0;
            }
        }
        i=0;j=1;
        while(true)
        {
            if(i<summary.size())
                result1+=summary.get(i);
            if(j<summary.size())
                result2+=summary.get(j);
            if(i>summary.size())
                break;
            i=i+2;
            j=j+2;
        }
        int num[]=new int[summary.size()];
        for (i=0;i<num.length;i++)
            num[i]=summary.get(i);
        return maxcount(num,0);
    }*/

}
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x)
    {
        val = x;
    }
}
